Date: Tue, 10 Dec 1996 16:51:49 GMT
Server: NCSA/1.4.2
Content-type: text/html

<HTML>
<head>
<title>CSE 321 Assignment #5</title>
</head>
<body>
<h1>CSE 321 Assignment #5<br>Autumn 1996</h1>
<h3>Due: Friday, November 1, 1996.
<br>

</h3>
<p>
Reading Assignment: Read handout on induction proofs for recursively defined
sets and sections 4.1-4.4 of the text.
The following problems are from the Third Edition of the text.
 
<p>
Practice Problems: page 210, problem 31;
<p> Problems: 
<ol>
<p><li> page 209, Problem 4.
<p><li> page 209, Problem 10.
<p><li> Give a recursive definition of the set of strings over alphabet
A={a,b} that have an even number of a's.  (You don't need to prove that it is
correct.)
<p><li> Define a set of strings S by:
<ul> 
<p><li> 1 is in S
<p><li> If x is in S and y is in S then the string x0y is in S
<p><li> (And no other strings are in S)
</ul>
<p>Give a recursive proof that every string in S has exactly one more 1 than it
has 0's.
<p><li> page 241, Problems 8, 12, and 20
<p><li> page 242, Problem 42.  (A restriction to 8 character variable names 
is one reason why the names of all those Unix commands are so obscure.)
<p><li> (Bonus) page 242, Problem 48.  (They just mean one column of the
truth table.)
<p><li> (Bonus) page 249, Problem 20.  
</ol>
</body>
</html>
